<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      // 快排 ： 先找到一个中间位置的值，根据中间位置的值将数据分为左右两部分 左边是比他小的部分 右边是比他大的部分
      //         左右两部分分好好后的数据继续递归执行步骤1
      //         直到分出的left 和right中的数组在3以内
      let arr = [5, 6, 2, 1, 3, 8, 7, 1.2, 5.5, 4.5];
      function quickSort(arr) {
        if (arr.length <= 1) {
          return arr;
        }
        let midValue = arr.splice([Math.floor((0 + arr.length - 1) / 2)], 1)[0];
        let left = [];
        let right = [];
        for (let i = 0; i < arr.length; i++) {
          if (arr[i] >= midValue) {
            right.push(arr[i]);
          } else {
            left.push(arr[i]);
          }
        }
        return [...quickSort(left), midValue, ...quickSort(right)];
      }
      // 插入排序 : 1 假定第一个元素是排好序的元素
      //            2 从第二个元素开始遍历 当前元素比前一个元素大说明顺序正确继续遍历
      //            3 如果比上一个元素小 就记录上一个元素的索引j 和 当前元素的值temp
      //            4 从上一个元素进行反向遍历 如果凡是比当前元素大的元素 就向前移动一位 直到遍历到比他小的或者是数组最开始的地方
      //            5 此时顺序就已经排列好 而反向遍历的索引j也就是当前比他小的值的位置 或者是数组的头部位置-1 也即是-1 那么就直接进行arr[j+1]=temp就可以了
      function sort(arr) {
        for (let i = 1; i < arr.length; i++) {
          if (arr[i] < arr[i - 1]) {
            let temp = arr[i];
            let j = i - 1;
            while (j >= 0 && arr[j] > temp) {
              arr[j + 1] = arr[j];
              j--;
            }
            arr[j + 1] = temp;
          }
        }
        return arr;
      }
      // 希尔排序 原则就是在插入排序的基础上先进行多次步长逐渐递减为1的插入排序
      // 说白就是比如数组长度为10 先进行步长为5 从5号位开始递增和当前位-5号位对比的插入排序 在进行步长为2从开始递增和当前位-2号位对比的插入排序 最后进行步长为1号位开始递增和当前位-1号位对比的插入排序

      let arr1 = [1, 4, 3, 6, 8, 11, 7, 9, 15, 11, 12, 22, 33, 14, 22];
      function shellSort(arr) {
        let gap = Math.floor(arr.length / 2);
        let len = arr.length;
        let temp;
        for (gap; gap > 0; gap = Math.floor(gap / 2)) {
          console.log(arr, gap);
          for (let i = gap; i < len; i++) {
            let j = i - gap;
            temp = arr[i];
            // gap和数组的
            while (j >= 0 && arr[j] > temp) {
              arr[j + 1] = arr[j];
              j -= gap;
            }
            arr[j + gap] = temp;
          }
        }
        return arr;
      }
      console.log(shellSort(arr1));
    </script>
  </body>
</html>
